From fda9110f5a493868f26f9c6075eeeeac23ec161d Mon Sep 17 00:00:00 2001
From: Brad Jorsch <anomie.wikipedia@gmail.com>
Date: Fri, 13 Jul 2012 14:56:17 -0400
Subject: [PATCH] (bug 35526) Make jquery.tablesorter use a stable sort

In r86337, jquery.tablesorter was changed from using the standard
Javascript Array.sort to a custom merge sort, with the justification
that it eliminates an eval and merge sort is stable. However, the
implementation used is not, in fact, stable, and making an in-place
merge sort stable reportedly kills performance.

Instead, let's just go back to using Array.sort, but with a closure
(basically the same comparison function used by the merge sort) rather
than an eval and using the already-calculated "position" as a tiebreaker
when two rows are otherwise equal to make it stable.

Change-Id: Idc50127d3bfec2b1727f397a9780b359fd56055e
---
 RELEASE-NOTES-1.20                            |  1 +
 resources/jquery/jquery.tablesorter.js        | 61 +++++--------------
 .../jquery/jquery.tablesorter.test.js         |  2 +-
 3 files changed, 17 insertions(+), 47 deletions(-)

diff --git a/RELEASE-NOTES-1.20 b/RELEASE-NOTES-1.20
index df7568d7b3..3b072c03a4 100644
--- a/RELEASE-NOTES-1.20
+++ b/RELEASE-NOTES-1.20
@@ -187,6 +187,7 @@ upgrade PHP if you have not done so prior to upgrading MediaWiki.
 * (bug 36073) Avoid duplicate element IDs on File pages
 * (bug 25095) Special:Categories should also include the first relevant item
   when "from" is filled.
+* (bug 35526) jquery.tablesorter now uses a stable sort.
 
 === API changes in 1.20 ===
 * (bug 34316) Add ability to retrieve maximum upload size from MediaWiki API.
diff --git a/resources/jquery/jquery.tablesorter.js b/resources/jquery/jquery.tablesorter.js
index 0edc8ee037..f28f401e16 100644
--- a/resources/jquery/jquery.tablesorter.js
+++ b/resources/jquery/jquery.tablesorter.js
@@ -337,55 +337,24 @@
 		return ( (b < a) ? false : ((b > a) ? true : 0) );
 	}
 
-	function checkSorting( array1, array2, sortList ) {
-		var col, fn, ret;
-		for ( var i = 0, len = sortList.length; i < len; i++ ) {
-			col = sortList[i][0];
-			fn = ( sortList[i][1] ) ? sortTextDesc : sortText;
-			ret = fn.call( this, array1[col], array2[col] );
-			if ( ret !== 0 ) {
-				return ret;
-			}
+	function multisort( table, sortList, cache ) {
+		var sortFn = [];
+		var len = sortList.length;
+		for ( var i = 0; i < len; i++ ) {
+			sortFn[i] = ( sortList[i][1] ) ? sortTextDesc : sortText;
 		}
-		return ret;
-	}
-
-	// Merge sort algorithm
-	// Based on http://en.literateprograms.org/Merge_sort_(JavaScript)
-	function mergeSortHelper( array, begin, beginRight, end, sortList ) {
-		for ( ; begin < beginRight; ++begin ) {
-			if ( checkSorting( array[begin], array[beginRight], sortList ) ) {
-				var v = array[begin];
-				array[begin] = array[beginRight];
-				var begin2 = beginRight;
-				while ( begin2 + 1 < end && checkSorting( v, array[begin2 + 1], sortList ) ) {
-					var tmp = array[begin2];
-					array[begin2] = array[begin2 + 1];
-					array[begin2 + 1] = tmp;
-					++begin2;
+		cache.normalized.sort( function ( array1, array2 ) {
+			var col, ret;
+			for ( var i = 0; i < len; i++ ) {
+				col = sortList[i][0];
+				ret = sortFn[i].call( this, array1[col], array2[col] );
+				if ( ret !== 0 ) {
+					return ret;
 				}
-				array[begin2] = v;
 			}
-		}
-	}
-
-	function mergeSort(array, begin, end, sortList) {
-		var size = end - begin;
-		if ( size < 2 ) {
-			return;
-		}
-
-		var beginRight = begin + Math.floor(size / 2);
-
-		mergeSort( array, begin, beginRight, sortList );
-		mergeSort( array, beginRight, end, sortList );
-		mergeSortHelper( array, begin, beginRight, end, sortList );
-	}
-
-	function multisort( table, sortList, cache ) {
-		var i = sortList.length;
-		mergeSort( cache.normalized, 0, cache.normalized.length, sortList );
-
+			// Fall back to index number column to ensure stable sort
+			return sortText.call( this, array1[array1.length - 1], array2[array2.length - 1] );
+		} );
 		return cache;
 	}
 
diff --git a/tests/qunit/suites/resources/jquery/jquery.tablesorter.test.js b/tests/qunit/suites/resources/jquery/jquery.tablesorter.test.js
index 2ec0941083..7d8c1d6044 100644
--- a/tests/qunit/suites/resources/jquery/jquery.tablesorter.test.js
+++ b/tests/qunit/suites/resources/jquery/jquery.tablesorter.test.js
@@ -298,7 +298,7 @@ tableTest(
 );
 
 var planetsRowspan = [["Earth","6051.8"], jupiter, ["Mars","6051.8"], mercury, saturn, venus];
-var planetsRowspanII = [jupiter, mercury, saturn, ['Venus', '6371.0'], venus, ['Venus', '3390.0']];
+var planetsRowspanII = [jupiter, mercury, saturn, venus, ['Venus', '6371.0'], ['Venus', '3390.0']];
 
 tableTest(
 	'Basic planet table: same value for multiple rows via rowspan',
-- 
2.20.1